New heuristics for the Max-Cut problem

Max-Cut (or, equivalently, Quadratic Unconstrained Binary Optimization (QUBO)) is one of the most relevant and studied combinatorial optimization problems. In the last decade, it got even more popularity after some innovative hardware, implementing heuristics that are based on quantum annealing, have been commercialized. These sys- tems (QPU) are not general-purpose computers; as a matter of fact, they are able only to provide good solutions to QUBO instances defined on Chimera graphs, but in amazingly short computing times. The availability of such systems propelled a great deal of research focused on transforming real-world optimization problems (machine learning among the many) to QUBO instances. The impact of the new technology became so strong that a QPU gained the cover page of TIME magazine in 2014. A speedup factor of thousands or even a million times of QPU over some classical heuristics has been reported in the scientific literature. In contrast, Selby proposes a heuristic that provides more accurate solutions than QPU in not much longer times. The heuristic is based on the so-called sub-graph sampling method. Essentially, the algorithm identifies a series of induced sub-graphs where Max-Cut is efficiently solvable due to their peculiar structure. Then the final solution is built from the solutions found on these sub-graphs. A recent study has shown that the Selby heuristic outperforms QPU both for solution quality and computing times. However, recently announced new versions of QPU can handle instances on graphs more complex than Chimera, whose tree-width is substantially higher, making Selby’s algorithm no longer applicable. This fact motivates this paper where, sticking to the same sub-graph sampling method, some structures of the induced sub-graphs, other than the tree-width, are exploited. In particular, two structures are considered: outer-planarity and the sign of the edge-weights, possibly after applying operations like subset contraction and switching that are commonly used in Max-Cut algorithms. The second structure makes it possible to apply the algorithm to any graph and not only to graphs with small tree-width like is the case for the algorithm of Selby. We tested the algorithm on toroidal grid graphs, on the Chimera graphs used in the mentioned study and on other instances in the literature obtaining encouraging results. For instance, we are able to find the optimal solution for 94.42% of the 1355 Chimera instances in less than 1.72 seconds when using 560 simultaneous threads. Also, running the algorithm with 560 different seeds per instance, we observed that the optimum is attained at least once every 20 repetitions.